home *** CD-ROM | disk | FTP | other *** search
/ Speccy ClassiX 1998 / Speccy ClassiX 98.iso / amiga_system / the_aminet / dev / gcc / ixemulsrc.lha / ixemul-41.4 / network / seq.c < prev    next >
C/C++ Source or Header  |  1995-05-18  |  8KB  |  319 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)seq.c    5.4 (Berkeley) 3/3/91";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include <sys/types.h>
  42. #include <errno.h>
  43. #include <db.h>
  44. #include <stdlib.h>
  45. #include "btree.h"
  46.  
  47. /*
  48.  *  _BT_SEQINIT -- Initialize a sequential scan on the btree.
  49.  *
  50.  *    Sets the tree's notion of the current scan location correctly
  51.  *    given a key and a direction.
  52.  *
  53.  *    Parameters:
  54.  *        t -- tree in which to initialize scan
  55.  *        key -- key for initial scan position
  56.  *        flags -- R_NEXT, R_PREV
  57.  *
  58.  *    Returns:
  59.  *        RET_SUCCESS, RET_ERROR, or RET_SPECIAL if there's no data
  60.  *        in the tree to scan.
  61.  *
  62.  *    Side Effects:
  63.  *        Changes current scan position for the tree.  Almost certainly
  64.  *        changes current page, as well.  Sets BTF_SEQINIT bit in tree
  65.  *        flags, so that we know we've initialized a scan.
  66.  */
  67.  
  68. int
  69. _bt_seqinit(t, key, flags)
  70.     BTREE_P t;
  71.     DBT *key;
  72.     int flags;
  73. {
  74.     BTITEM *item;
  75.     BTHEADER *h;
  76.     CURSOR *c;
  77.     IDATUM *id;
  78.     index_t last;
  79.  
  80.     /*
  81.      *  Figure out if we really have to search for the key that the
  82.      *  user supplied.  If key is null, then this is an unkeyed scan
  83.      *  and we can just start from an endpoint.
  84.      */
  85.  
  86.     c = &(t->bt_cursor);
  87.  
  88.     if (flags == R_CURSOR) {
  89.         if (key->data != (u_char *) NULL) {
  90.  
  91.             /* key supplied, find first instance of it */
  92.             item = _bt_first(t, key);
  93.             c->c_index = item->bti_index;
  94.             c->c_pgno = t->bt_curpage->h_pgno;
  95.         } else {
  96.             errno = EINVAL;
  97.             return (RET_ERROR);
  98.         }
  99.  
  100.     } else {
  101.  
  102.         /*
  103.          *  Unkeyed scan.  For backward scans, find the last item
  104.          *  in the tree; for forward scans, find the first item.
  105.          */
  106.  
  107.         if (_bt_getpage(t, (pgno_t) P_ROOT) == RET_ERROR)
  108.             return (RET_ERROR);
  109.         h = t->bt_curpage;
  110.         if (flags == R_LAST || flags == R_PREV) {
  111.  
  112.             /* backward scan */
  113.             while (!(h->h_flags & F_LEAF)) {
  114.                 last = NEXTINDEX(h) - 1;
  115.                 id = (IDATUM *) GETDATUM(h,last);
  116.                 if (_bt_getpage(t, id->i_pgno) == RET_ERROR)
  117.                     return (RET_ERROR);
  118.                 h = t->bt_curpage;
  119.             }
  120.  
  121.             /* skip empty pages */
  122.             while (NEXTINDEX(h) == 0 && h->h_prevpg != P_NONE) {
  123.                 if (_bt_getpage(t, h->h_prevpg) == RET_ERROR)
  124.                     return (RET_ERROR);
  125.                 h = t->bt_curpage;
  126.             }
  127.  
  128.             c->c_pgno = h->h_pgno;
  129.             if (NEXTINDEX(h) > 0)
  130.                 c->c_index = NEXTINDEX(h) - 1;
  131.             else
  132.                 c->c_index = 0;
  133.         } else if (flags == R_FIRST || flags == R_NEXT) {
  134.             /* forward scan */
  135.             while (!(h->h_flags & F_LEAF)) {
  136.                 id = (IDATUM *) GETDATUM(h,0);
  137.                 if (_bt_getpage(t, id->i_pgno) == RET_ERROR)
  138.                     return (RET_ERROR);
  139.                 h = t->bt_curpage;
  140.             }
  141.  
  142.             /* skip empty pages */
  143.             while (NEXTINDEX(h) == 0 && h->h_nextpg != P_NONE) {
  144.                 if (_bt_getpage(t, h->h_nextpg) == RET_ERROR)
  145.                     return (RET_ERROR);
  146.                 h = t->bt_curpage;
  147.             }
  148.  
  149.             c->c_pgno = h->h_pgno;
  150.             c->c_index = 0;
  151.         } else {
  152.             /* no flags passed in */
  153.             errno = EINVAL;
  154.             return (RET_ERROR);
  155.         }
  156.     }
  157.  
  158.     /* okay, scan is initialized */
  159.     t->bt_flags |= BTF_SEQINIT;
  160.  
  161.     /* don't need the descent stack anymore */
  162.     while (_bt_pop(t) != P_NONE)
  163.         continue;
  164.  
  165.     if (c->c_index == NEXTINDEX(t->bt_curpage))
  166.         return (RET_SPECIAL);
  167.  
  168.     return (RET_SUCCESS);
  169. }
  170.  
  171. /*
  172.  *  _BT_SEQADVANCE -- Advance the sequential scan on this tree.
  173.  *
  174.  *    Moves the current location pointer for the scan on this tree one
  175.  *    spot in the requested direction.
  176.  *
  177.  *    Parameters:
  178.  *        t -- btree being scanned
  179.  *        flags -- for R_NEXT, R_PREV
  180.  *
  181.  *    Returns:
  182.  *        RET_SUCCESS, RET_ERROR, or RET_SPECIAL if there is no
  183.  *        more data in the specified direction.
  184.  *
  185.  *    Side Effects:
  186.  *        May change current page.
  187.  */
  188.  
  189. int
  190. _bt_seqadvance(t, flags)
  191.     BTREE_P t;
  192.     int flags;
  193. {
  194.     BTHEADER *h;
  195.     CURSOR *c;
  196.     index_t index;
  197.  
  198.     c = &(t->bt_cursor);
  199.     index = c->c_index;
  200.  
  201.     if (_bt_getpage(t, c->c_pgno) == RET_ERROR)
  202.         return (RET_ERROR);
  203.     h = t->bt_curpage;
  204.  
  205.     /* by the time we get here, don't need the cursor key anymore */
  206.     if (c->c_key != (char *) NULL)
  207.         (void) free(c->c_key);
  208.  
  209.     if (flags == R_NEXT) {
  210.  
  211.         /*
  212.          *  This is a forward scan.  If the cursor is pointing
  213.          *  at a virtual record (that is, it was pointing at
  214.          *  a record that got deleted), then we should return
  215.          *  the record it's pointing at now.  Otherwise, we
  216.          *  should advance the scan.  In either case, we need
  217.          *  to be careful not to run off the end of the current
  218.          *  page.
  219.          */
  220.  
  221.         if (c->c_flags & CRSR_BEFORE) {
  222.  
  223.             if (index >= NEXTINDEX(h)) {
  224.                 /* out of items on this page, get next page */
  225.                 if (h->h_nextpg == P_NONE) {
  226.                     /* tell caller we're done... */
  227.                     c->c_index = NEXTINDEX(h);
  228.                     return (RET_SPECIAL);
  229.                 }
  230.  
  231.                 /* skip empty pages */
  232.                 do {
  233.                     if (_bt_getpage(t, h->h_nextpg)
  234.                         == RET_ERROR) {
  235.                         c->c_index = NEXTINDEX(h);
  236.                         return (RET_ERROR);
  237.                     }
  238.                     h = t->bt_curpage;
  239.                     c->c_pgno = h->h_pgno;
  240.                 } while (NEXTINDEX(h) == 0
  241.                      && h->h_nextpg != P_NONE);
  242.  
  243.                 if (NEXTINDEX(h) == 0) {
  244.                     /* tell caller we're done */
  245.                     c->c_index = NEXTINDEX(h);
  246.                     return (RET_SPECIAL);
  247.                 }
  248.                 index = 0;
  249.             }
  250.             c->c_flags &= ~CRSR_BEFORE;
  251.  
  252.         } else if (++index >= NEXTINDEX(h)) {
  253.  
  254.             /* out of items on this page, get next page */
  255.             if (h->h_nextpg == P_NONE) {
  256.                 /* tell caller we're done... */
  257.                 c->c_index = NEXTINDEX(h);
  258.                 return (RET_SPECIAL);
  259.             }
  260.  
  261.             /* skip empty pages */
  262.             do {
  263.                 if (_bt_getpage(t, h->h_nextpg) == RET_ERROR) {
  264.                     c->c_index = NEXTINDEX(h);
  265.                     return (RET_ERROR);
  266.                 }
  267.                 h = t->bt_curpage;
  268.                 c->c_pgno = h->h_pgno;
  269.             } while (NEXTINDEX(h) == 0 && h->h_nextpg != P_NONE);
  270.  
  271.             if (NEXTINDEX(h) == 0) {
  272.                 /* tell caller we're done */
  273.                 c->c_index = NEXTINDEX(h);
  274.                 return (RET_SPECIAL);
  275.             }
  276.             index = 0;
  277.         }
  278.     } else if (flags == R_PREV) {
  279.  
  280.         /* for backward scans, life is substantially easier */
  281.         c->c_flags &= ~CRSR_BEFORE;
  282.         if (c->c_key != (char *) NULL) {
  283.             (void) free(c->c_key);
  284.             c->c_key = (char *) NULL;
  285.         }
  286.  
  287.         if (index == 0) {
  288.  
  289.             /* we may be done */
  290.             c->c_index = 0;
  291.  
  292.             /* out of items on this page, get next page */
  293.             if (h->h_prevpg == P_NONE)
  294.                 return (RET_SPECIAL);
  295.  
  296.             /* skip empty pages */
  297.             do {
  298.                 if (_bt_getpage(t, h->h_prevpg) == RET_ERROR)
  299.                     return (RET_ERROR);
  300.                 h = t->bt_curpage;
  301.                 c->c_pgno = h->h_pgno;
  302.             } while (NEXTINDEX(h) == 0 && h->h_prevpg != P_NONE);
  303.  
  304.             if (NEXTINDEX(h) == 0)
  305.                 return (RET_SPECIAL);
  306.  
  307.             index = NEXTINDEX(h) - 1;
  308.         } else
  309.             --index;
  310.     } else {
  311.         /* must specify a direction */
  312.         errno = EINVAL;
  313.         return (RET_ERROR);
  314.     }
  315.  
  316.     c->c_index = index;
  317.     return (RET_SUCCESS);
  318. }
  319.